home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 7: Sunsite / Linux Cubed Series 7 - Sunsite Vol 1.iso / system / filesyst / dosfs / dmsdosfs.000 / dmsdosfs / dmsdosfs-0.6.9b / dmsdos_compr.c < prev    next >
C/C++ Source or Header  |  1996-07-29  |  14KB  |  484 lines
  1. /*
  2.  
  3. linux/fs/dmsdos/dmsdos_compr.c
  4.  
  5. DMSDOS filesystem: compression routines
  6.  
  7. ******************************************************************************
  8. DMSDOS (Doublespace/Drivespace compressed MSDOS filesystem) for Linux
  9. written 1995,1996 by Frank Gockel
  10.  
  11.     (C) Copyright 1995,1996 by Frank Gockel
  12.  
  13. Some code of the dmsdos filesystem has been copied from the msdos filesystem
  14. so there are the following additional copyrights:
  15.  
  16.     (C) Copyright 1992,1993 by Werner Almesberger (msdos filesystem)
  17.     (C) Copyright 1994,1995 by Jacques Gelinas (mmap code)
  18.     (C) Copyright 1992-1995 by Linus Torvalds
  19.  
  20. The DMSDOS filesystem was inspired by the THS filesystem (a simple doublespace
  21. DS-0-2 compressed read-only filesystem) written 1994 by Thomas Scheuermann.
  22.  
  23. The DMSDOS filesystem is distributed under the Gnu General Public Licence.
  24. See file COPYING for details.
  25. ******************************************************************************
  26.  
  27. */
  28.  
  29. #include <linux/errno.h>
  30. #include <linux/kernel.h>
  31. #include <linux/malloc.h>
  32. #include <linux/fs.h>
  33. #include <linux/msdos_fs.h>
  34. #include <linux/dmsdos_fs.h>
  35.  
  36. /* undef this to avoid compression */
  37. #define DBL_COMPRESSION
  38.  
  39. /* GUESS_HACK forces the compression scheme guessing code to return JM-0-1 as
  40.    result when it in fact has guessed SQ-0-0. This is because SQ-0-0 is
  41.    currently unsupported, so write access would be always uncompressed on
  42.    SQ-0-0 compressed drives. 'undef' this to avoid this hack */ 
  43. #define GUESS_HACK
  44.  
  45. #ifdef __KERNEL__
  46. extern Dblsb dblsb[];
  47. #else
  48. extern int cfaktor;
  49. void panic(char*);
  50. #endif /*__KERNEL__*/
  51.  
  52. /* maybe the values have to be adapted for optimal compression/speed 
  53.    relationship */
  54. int c_maxdiff[12]={ 63, 63, 63, 63,319,319,319,319,4414,4414,4414,4414};
  55. int c_maxlen[12] ={ 64,128,256,512, 64,128,256,512,  64, 128, 256, 512};
  56.  
  57. inline void putbit(unsigned char*clusterk,int*zielpos,int*zielmask,int bit)
  58. {
  59.   if(bit)clusterk[*zielpos]|=*zielmask;
  60.   else clusterk[*zielpos]&=~(*zielmask);
  61.   (*zielmask)<<=1;
  62.   if(*zielmask==256)
  63.   { *zielmask=1;
  64.     ++(*zielpos);
  65.   }
  66. }
  67.  
  68. void putbits(unsigned char*clusterk,int*zielpos,int*zielmask,int byte,int anz)
  69. { int i;
  70.   int mask;
  71.   
  72.   mask=1;
  73.   for(i=0;i<anz;++i)
  74.   { putbit(clusterk,zielpos,zielmask,byte&mask);
  75.     mask<<=1;
  76.   }
  77. }
  78.  
  79. void write_byte(unsigned char*clusterk,int*zielpos,int*zielmask,int byte,
  80.                 int method)
  81. { if(method!=JM_0_0&&method!=JM_0_1)
  82.   { if(byte<128)putbits(clusterk,zielpos,zielmask,2,2);
  83.     else putbits(clusterk,zielpos,zielmask,1,2);
  84.   }
  85.   else /* JM_0_0 */
  86.   { if(byte<128)putbit(clusterk,zielpos,zielmask,0);
  87.     else putbits(clusterk,zielpos,zielmask,3,2);
  88.   }
  89.   putbits(clusterk,zielpos,zielmask,byte,7);
  90. }
  91.  
  92. void write_temp(unsigned char*clusterk,int*zielpos,int*zielmask,
  93.                 unsigned char*tempstr,int len,int diff,int method)
  94. { if(len==1)
  95.   { write_byte(clusterk,zielpos,zielmask,tempstr[0],method);
  96.     return;
  97.   }
  98.   if(len==2&&(method==JM_0_0||method==JM_0_1))
  99.   { write_byte(clusterk,zielpos,zielmask,tempstr[0],method);
  100.     write_byte(clusterk,zielpos,zielmask,tempstr[1],method);
  101.     return;
  102.   }
  103.   if(method!=JM_0_0&&method!=JM_0_1)
  104.   { ++len; /* corrects different counting scheme */
  105.     if(diff<64)putbits(clusterk,zielpos,zielmask,0,2);
  106.     else putbits(clusterk,zielpos,zielmask,3,2);
  107.   }
  108.   else /* JM_0_0 */
  109.   { putbits(clusterk,zielpos,zielmask,1,2);
  110.     putbit(clusterk,zielpos,zielmask,(diff<64)?0:1);
  111.   }
  112.   if(diff<64)putbits(clusterk,zielpos,zielmask,diff,6);
  113.   else 
  114.   { if(diff<320)
  115.     { putbit(clusterk,zielpos,zielmask,0);
  116.       putbits(clusterk,zielpos,zielmask,diff-64,8);
  117.     }
  118.     else
  119.     { putbit(clusterk,zielpos,zielmask,1);
  120.       putbits(clusterk,zielpos,zielmask,diff-320,12);
  121.     }
  122.   }
  123.   /* okay, now encode len */
  124.   if(len==3)
  125.   { putbit(clusterk,zielpos,zielmask,1);
  126.     return;
  127.   }
  128.   putbit(clusterk,zielpos,zielmask,0);
  129.   if(len<6)
  130.   { putbit(clusterk,zielpos,zielmask,1);
  131.     putbit(clusterk,zielpos,zielmask,len-4);
  132.     return;
  133.   }
  134.   putbit(clusterk,zielpos,zielmask,0);
  135.   if(len<10)
  136.   { putbit(clusterk,zielpos,zielmask,1);
  137.     putbits(clusterk,zielpos,zielmask,len-6,2);
  138.     return;
  139.   }
  140.   putbit(clusterk,zielpos,zielmask,0);
  141.   if(len<18)
  142.   { putbit(clusterk,zielpos,zielmask,1);
  143.     putbits(clusterk,zielpos,zielmask,len-10,3);
  144.     return;
  145.   }
  146.   putbit(clusterk,zielpos,zielmask,0);
  147.   if(len<34)
  148.   { putbit(clusterk,zielpos,zielmask,1);
  149.     putbits(clusterk,zielpos,zielmask,len-18,4);
  150.     return;
  151.   }
  152.   putbit(clusterk,zielpos,zielmask,0);
  153.   if(len<66)
  154.   { putbit(clusterk,zielpos,zielmask,1);
  155.     putbits(clusterk,zielpos,zielmask,len-34,5);
  156.     return;
  157.   }
  158.   putbit(clusterk,zielpos,zielmask,0);
  159.   if(len<130)
  160.   { putbit(clusterk,zielpos,zielmask,1);
  161.     putbits(clusterk,zielpos,zielmask,len-66,6);
  162.     return;
  163.   }
  164.   putbit(clusterk,zielpos,zielmask,0);
  165.   if(len<258)
  166.   { putbit(clusterk,zielpos,zielmask,1);
  167.     putbits(clusterk,zielpos,zielmask,len-130,7);
  168.     return;
  169.   }
  170.   putbit(clusterk,zielpos,zielmask,0);
  171.   putbit(clusterk,zielpos,zielmask,1);
  172.   putbits(clusterk,zielpos,zielmask,len-258,8);
  173. }
  174.  
  175. void write_marker(unsigned char*clusterk,int*zielpos,int*zielmask,int method)
  176. { if(method==JM_0_0||method==JM_0_1)putbits(clusterk,zielpos,zielmask,13,4);
  177.   else /* DS_0_x */ putbits(clusterk,zielpos,zielmask,7,3);
  178.   putbits(clusterk,zielpos,zielmask,0xFFF,12); 
  179. }
  180.  
  181. inline int such_rb_byte(unsigned char*clusterd, int byte, int ab)
  182. { while(ab>=0)
  183.   { if(byte==clusterd[ab])return ab;
  184.     --ab;
  185.   }
  186.   return -1;
  187. }
  188.  
  189. inline int mystrncmp(unsigned char*a,unsigned char*b,int len)
  190. { --len;
  191.   while(len>=0)
  192.   { if(a[len]!=b[len])return 1;
  193.     --len;
  194.   }
  195.   return 0;
  196. }
  197.  
  198. inline int such_rb_string(unsigned char*clusterd,unsigned char*tempstr,int ab,
  199.                    int len)
  200. { while(ab>=0)
  201.   { if(mystrncmp(tempstr,&(clusterd[ab]),len)==0)return ab;
  202.     --ab;
  203.   }
  204.   return -1;
  205. }                   
  206.  
  207. /* compresses a cluster 
  208.    gets uncompressed size (number of used sectors)
  209.    returns compressed size (in number of used sectors) or -1 if failed
  210. */
  211. int compress(unsigned char* clusterk, unsigned char* clusterd, int size,
  212.              int method,int cvfnr)
  213. { 
  214.  
  215. #ifdef DBL_COMPRESSION
  216.  
  217.   int i;
  218.   int j;
  219.   int zielpos;
  220.   int zielmask;
  221.   int pos;
  222.   int lentemp;
  223.   int maxzielpos;
  224.   int byte;
  225.   int rb_pos=0; /* avoids warning */
  226.   int rb_beg=0; /* avoids warning */
  227.   int last_rb_pos;
  228. #ifdef __KERNEL__
  229.   int maxdiff=c_maxdiff[dblsb[cvfnr].s_cfaktor];
  230.   int maxlen=c_maxlen[dblsb[cvfnr].s_cfaktor];
  231. #else
  232.   int maxdiff=c_maxdiff[cfaktor];
  233.   int maxlen=c_maxlen[cfaktor];
  234. #endif /*__KERNEL__*/
  235.  
  236.   switch(method)
  237.   { case DS_0_0:
  238.     case DS_0_1:
  239.     case DS_0_2: /* handled together with JM_0_0 because similar */
  240.     case JM_0_0:
  241.     case JM_0_1:
  242.  
  243.       zielpos=0;
  244.       zielmask=1;
  245.       pos=0;
  246.       lentemp=0;
  247.       maxzielpos=(size-1)*512;
  248.       
  249.       /* put magic number */
  250.       putbits(clusterk,&zielpos,&zielmask,method,32);
  251.       
  252.       for(i=0;i<size;++i)
  253.       { for(j=0;j<512;++j)
  254.         { byte=clusterd[i*512+j];
  255.         
  256.           /* begin compression algorithm (sorry for using gotos...) */
  257.           
  258.           retry:
  259.             if(pos==0) /* hmm... first byte, nothing to compress */
  260.             { write_byte(clusterk,&zielpos,&zielmask,byte,method);
  261.               ++pos;
  262.               goto end;
  263.             }
  264.             
  265.             if(lentemp==0)
  266.             { rb_pos=such_rb_byte(clusterd,byte,pos-1);
  267.               if(rb_pos<0||pos-rb_pos>maxdiff)
  268.               { write_byte(clusterk,&zielpos,&zielmask,byte,method);
  269.                 ++pos;
  270.                 goto end;
  271.               }
  272.               rb_beg=pos;
  273.               lentemp=1;
  274.               ++pos;
  275.               goto end;
  276.             }
  277.             
  278.             else
  279.             { ++lentemp;
  280.               if(lentemp+rb_pos>rb_beg) goto norb;
  281.               if(byte!=clusterd[rb_pos+lentemp-1]) goto norb;
  282.               if(lentemp==maxlen)
  283.               { write_temp(clusterk,&zielpos,&zielmask,&(clusterd[rb_beg]),
  284.                            lentemp,rb_beg-rb_pos,method);
  285.                 lentemp=0;
  286.               }
  287.               ++pos;
  288.               goto end;
  289.               
  290.             norb:
  291.               last_rb_pos=rb_pos;
  292.               rb_pos=such_rb_string(clusterd,&(clusterd[rb_beg]),
  293.                                     rb_beg-lentemp,lentemp);
  294.               if(rb_pos<0||rb_beg-rb_pos>maxdiff)
  295.               { --lentemp;
  296.                 write_temp(clusterk,&zielpos,&zielmask,&(clusterd[rb_beg]),
  297.                            lentemp,rb_beg-last_rb_pos,method);
  298.                 lentemp=0;
  299.                 goto retry;
  300.               }
  301.               ++pos;
  302.             }
  303.             
  304.           /* end compression algorithm */
  305.           
  306.           end:
  307.             if(zielpos>maxzielpos)return -1; /* incompressible data */
  308.           
  309.         }
  310.         if(lentemp>0)
  311.         { write_temp(clusterk,&zielpos,&zielmask,&(clusterd[rb_beg]),
  312.                      lentemp,rb_beg-rb_pos,method);
  313.           lentemp=0;
  314.         }
  315.         write_marker(clusterk,&zielpos,&zielmask,method);
  316.       }
  317.       
  318.       if(zielpos>maxzielpos)return -1;
  319.       if(zielmask!=1)++zielpos; /* last byte is only used if mask != 1 */
  320.       return (zielpos-1)/512+1;
  321.       
  322.     default: 
  323.       /* sorry, other compression methods currently not available */
  324.       return -1; 
  325.   }
  326.   
  327. #endif
  328.  
  329.   return -1;
  330. }
  331.  
  332. /* write a dmsdos cluster, compress before if possible;
  333.    length is the number of used bytes, may be < SECTOR_SIZE*sectperclust only
  334.    in the last cluster of a file;
  335.    cluster must be allocated by allocate_cluster before if it is a new one;
  336.    unable to write dir clusters;
  337.    to avoid MDFAT level fragmentation, near_sector should be the sector no
  338.    of the preceeding cluster;
  339.    if ucflag>0 uncompressed write is forced (only for umsdos --linux-.---)
  340.    if ucflag<0 raw write is forced with compressed size -ucflag (in sectors).
  341. */
  342.  
  343. #ifdef __KERNEL__
  344.  
  345. int dmsdos_write_cluster(struct super_block*sb,
  346.                          unsigned char* clusterd, int length, int clusternr,
  347.                          int near_sector, int cvfnr, int ucflag)
  348. { int method;
  349.   unsigned char* clusterk;
  350.   int size;
  351.   Mdfat_entry mde;
  352.   int sektor;
  353.   int i;
  354.   int res;
  355.   int ksize;
  356.   struct buffer_head*bh;
  357.  
  358.   LOCK_READWRITE;  
  359.   /*printk("DMSDOS write_cluster clusternr=%d length=%d near_sector=%d cvfnr=%d\n",
  360.          clusternr,length,near_sector,cvfnr);*/
  361.  
  362.   /* guess compression method if not already known */
  363.   if(dblsb[cvfnr].s_comp==GUESS)
  364.   { 
  365.     printk("DMSDOS: write_cluster: guessing compression method...\n");
  366.     for(i=2;i<=dblsb[cvfnr].s_max_cluster;++i)
  367.     { dbl_mdfat_value(sb,i,cvfnr,NULL,&mde);
  368.       /*if((mdfat&0xC0000000)==0x80000000)*/
  369.       if(mde.flags==2)
  370.       { bh=read_dbl_sector(sb,mde.sector_minus_1+1,cvfnr);
  371.         if(bh!=NULL)
  372.         {
  373.           res=CHL(bh->b_data);
  374.           bh_free(sb,bh);
  375.           if(res==DS_0_0){dblsb[cvfnr].s_comp=DS_0_0;goto guess_ok;}
  376.           if(res==DS_0_1){dblsb[cvfnr].s_comp=DS_0_1;goto guess_ok;}
  377.           if(res==DS_0_2){dblsb[cvfnr].s_comp=DS_0_2;goto guess_ok;}
  378.           if(res==JM_0_0){dblsb[cvfnr].s_comp=JM_0_0;goto guess_ok;}
  379.           if(res==JM_0_1){dblsb[cvfnr].s_comp=JM_0_1;goto guess_ok;}
  380.           if(res==SQ_0_0){dblsb[cvfnr].s_comp=SQ_0_0;goto guess_ok;}
  381.         }
  382.       }
  383.     }
  384.     printk("DMSDOS: could not guess compression method for CVF %d\n",cvfnr+1);
  385.     dblsb[cvfnr].s_comp=UNCOMPRESSED;
  386.     
  387.     guess_ok:
  388.     printk("DMSDOS: write_cluster: guessed 0x%08x.\n",dblsb[cvfnr].s_comp);
  389. #ifdef GUESS_HACK
  390.     if(dblsb[cvfnr].s_comp==SQ_0_0)
  391.     { dblsb[cvfnr].s_comp=JM_0_1;
  392.       printk("DMSDOS: guess_hack: guessed SQ-0-0 not supported, using JM-0-1 instead.\n");
  393.     }
  394. #endif
  395.   }
  396.   
  397.   method=dblsb[cvfnr].s_comp; /* default compression method */
  398.   
  399.   size=(length-1)/512+1;
  400.   if(size==1||ucflag!=0)method=UNCOMPRESSED; /* will not become smaller */
  401.   
  402.   if(method==UNCOMPRESSED) /* includes RAW write */
  403.   { clusterk=clusterd;
  404.     if(ucflag<0)
  405.     { /* raw write of already compressed data (for dmsdosd/ioctl) */
  406.       ksize=-ucflag;
  407.       mde.size_lo_minus_1=ksize-1;
  408.       mde.size_hi_minus_1=size-1;
  409.       mde.flags=2;
  410.     }
  411.     else
  412.     { /* normal uncompressed write */
  413.       /*mdfat=0xC0000000|((size-1)<<26)|((size-1)<<22);*/
  414.       mde.size_lo_minus_1=size-1;
  415.       mde.size_hi_minus_1=size-1;
  416.       mde.flags=3;
  417.       ksize=size;
  418.     }
  419.   }
  420.   else
  421.   { if(try_daemon(clusternr,cvfnr,length,method))goto wr_uc;
  422.     clusterk=(unsigned char*)MALLOC(size*SECTOR_SIZE);
  423.     if(clusterk==NULL)
  424.     { printk("DMSDOS: write_cluster: no memory for compression, writing uncompressed!\n");
  425.   wr_uc:  
  426.       clusterk=clusterd;
  427.       /*mdfat=0xC0000000|((size-1)<<26)|((size-1)<<22);*/
  428.       mde.size_lo_minus_1=size-1;
  429.       mde.size_hi_minus_1=size-1;
  430.       mde.flags=3;
  431.       method=UNCOMPRESSED;
  432.       ksize=size;
  433.     }
  434.     else 
  435.     { /*printk("DMSDOS: write_cluster: compressing...\n");*/
  436.       ksize=compress(clusterk,clusterd,size,method,cvfnr);
  437.       /*printk("DMSDOS: write cluster: compressing finished\n");*/
  438.       if(ksize<0)
  439.       { /* compression failed */
  440.         FREE(clusterk);
  441.         clusterk=clusterd;
  442.         /*mdfat=0xC0000000|((size-1)<<26)|((size-1)<<22);*/
  443.         mde.size_lo_minus_1=size-1;
  444.         mde.size_hi_minus_1=size-1;
  445.         mde.flags=3;
  446.         method=UNCOMPRESSED;
  447.         ksize=size;
  448.       }
  449.       else
  450.       { /*mdfat=0x80000000|((size-1)<<26)|((ksize-1)<<22);*/
  451.         mde.size_lo_minus_1=ksize-1;
  452.         mde.size_hi_minus_1=size-1;
  453.         mde.flags=2;
  454.       }
  455.     }
  456.   }
  457.   
  458.   /*printk("DMSDOS: write_cluster: call replace_existing_cluster mdfat=0x%x\n",
  459.          mdfat);*/
  460.   sektor=replace_existing_cluster(sb,clusternr,near_sector,&mde,cvfnr);
  461.   /*printk("DMSDOS: write_cluster: replace_existing_cluster returned %d\n",
  462.          sektor);*/
  463.   if(sektor<0)res=-ENOSPC;
  464.   else
  465.   { res=0;
  466.     for(i=0;i<ksize;++i)
  467.     { bh=noread_dbl_sector(sb,sektor+i,cvfnr);
  468.       if(bh==NULL)res=-EIO;
  469.       else
  470.       {
  471.         memcpy(bh->b_data,&(clusterk[SECTOR_SIZE*i]),SECTOR_SIZE);
  472.         bh_dirty(sb,bh);
  473.         bh_free(sb,bh);
  474.       }
  475.     }
  476.   }
  477.   
  478.   if(method!=UNCOMPRESSED)FREE(clusterk);
  479.   
  480.   UNLOCK_READWRITE;
  481.   return res;
  482. }
  483.  
  484. #endif /*__KERNEL__*/